0 CpxTRS
↳1 TrsToWeightedTrsProof (BOTH BOUNDS(ID, ID), 0 ms)
↳2 CpxWeightedTrs
↳3 CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID), 0 ms)
↳4 CpxWeightedTrs
↳5 InnermostUnusableRulesProof (BOTH BOUNDS(ID, ID), 0 ms)
↳6 CpxWeightedTrs
↳7 TypeInferenceProof (BOTH BOUNDS(ID, ID), 0 ms)
↳8 CpxTypedWeightedTrs
↳9 CompletionProof (UPPER BOUND(ID), 0 ms)
↳10 CpxTypedWeightedCompleteTrs
↳11 CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID), 14 ms)
↳12 CpxRNTS
↳13 CompleteCoflocoProof (⇔, 3960 ms)
↳14 BOUNDS(1, n^2)
U11(tt, V1, V2) → U12(isNatKind(activate(V1)), activate(V1), activate(V2))
U12(tt, V1, V2) → U13(isNatKind(activate(V2)), activate(V1), activate(V2))
U13(tt, V1, V2) → U14(isNatKind(activate(V2)), activate(V1), activate(V2))
U14(tt, V1, V2) → U15(isNat(activate(V1)), activate(V2))
U15(tt, V2) → U16(isNat(activate(V2)))
U16(tt) → tt
U21(tt, V1) → U22(isNatKind(activate(V1)), activate(V1))
U22(tt, V1) → U23(isNat(activate(V1)))
U23(tt) → tt
U31(tt, V2) → U32(isNatKind(activate(V2)))
U32(tt) → tt
U41(tt) → tt
U51(tt, N) → U52(isNatKind(activate(N)), activate(N))
U52(tt, N) → activate(N)
U61(tt, M, N) → U62(isNatKind(activate(M)), activate(M), activate(N))
U62(tt, M, N) → U63(isNat(activate(N)), activate(M), activate(N))
U63(tt, M, N) → U64(isNatKind(activate(N)), activate(M), activate(N))
U64(tt, M, N) → s(plus(activate(N), activate(M)))
isNat(n__0) → tt
isNat(n__plus(V1, V2)) → U11(isNatKind(activate(V1)), activate(V1), activate(V2))
isNat(n__s(V1)) → U21(isNatKind(activate(V1)), activate(V1))
isNatKind(n__0) → tt
isNatKind(n__plus(V1, V2)) → U31(isNatKind(activate(V1)), activate(V2))
isNatKind(n__s(V1)) → U41(isNatKind(activate(V1)))
plus(N, 0) → U51(isNat(N), N)
plus(N, s(M)) → U61(isNat(M), M, N)
0 → n__0
plus(X1, X2) → n__plus(X1, X2)
s(X) → n__s(X)
activate(n__0) → 0
activate(n__plus(X1, X2)) → plus(X1, X2)
activate(n__s(X)) → s(X)
activate(X) → X
U11(tt, V1, V2) → U12(isNatKind(activate(V1)), activate(V1), activate(V2)) [1]
U12(tt, V1, V2) → U13(isNatKind(activate(V2)), activate(V1), activate(V2)) [1]
U13(tt, V1, V2) → U14(isNatKind(activate(V2)), activate(V1), activate(V2)) [1]
U14(tt, V1, V2) → U15(isNat(activate(V1)), activate(V2)) [1]
U15(tt, V2) → U16(isNat(activate(V2))) [1]
U16(tt) → tt [1]
U21(tt, V1) → U22(isNatKind(activate(V1)), activate(V1)) [1]
U22(tt, V1) → U23(isNat(activate(V1))) [1]
U23(tt) → tt [1]
U31(tt, V2) → U32(isNatKind(activate(V2))) [1]
U32(tt) → tt [1]
U41(tt) → tt [1]
U51(tt, N) → U52(isNatKind(activate(N)), activate(N)) [1]
U52(tt, N) → activate(N) [1]
U61(tt, M, N) → U62(isNatKind(activate(M)), activate(M), activate(N)) [1]
U62(tt, M, N) → U63(isNat(activate(N)), activate(M), activate(N)) [1]
U63(tt, M, N) → U64(isNatKind(activate(N)), activate(M), activate(N)) [1]
U64(tt, M, N) → s(plus(activate(N), activate(M))) [1]
isNat(n__0) → tt [1]
isNat(n__plus(V1, V2)) → U11(isNatKind(activate(V1)), activate(V1), activate(V2)) [1]
isNat(n__s(V1)) → U21(isNatKind(activate(V1)), activate(V1)) [1]
isNatKind(n__0) → tt [1]
isNatKind(n__plus(V1, V2)) → U31(isNatKind(activate(V1)), activate(V2)) [1]
isNatKind(n__s(V1)) → U41(isNatKind(activate(V1))) [1]
plus(N, 0) → U51(isNat(N), N) [1]
plus(N, s(M)) → U61(isNat(M), M, N) [1]
0 → n__0 [1]
plus(X1, X2) → n__plus(X1, X2) [1]
s(X) → n__s(X) [1]
activate(n__0) → 0 [1]
activate(n__plus(X1, X2)) → plus(X1, X2) [1]
activate(n__s(X)) → s(X) [1]
activate(X) → X [1]
| 0 => 0' |
U11(tt, V1, V2) → U12(isNatKind(activate(V1)), activate(V1), activate(V2)) [1]
U12(tt, V1, V2) → U13(isNatKind(activate(V2)), activate(V1), activate(V2)) [1]
U13(tt, V1, V2) → U14(isNatKind(activate(V2)), activate(V1), activate(V2)) [1]
U14(tt, V1, V2) → U15(isNat(activate(V1)), activate(V2)) [1]
U15(tt, V2) → U16(isNat(activate(V2))) [1]
U16(tt) → tt [1]
U21(tt, V1) → U22(isNatKind(activate(V1)), activate(V1)) [1]
U22(tt, V1) → U23(isNat(activate(V1))) [1]
U23(tt) → tt [1]
U31(tt, V2) → U32(isNatKind(activate(V2))) [1]
U32(tt) → tt [1]
U41(tt) → tt [1]
U51(tt, N) → U52(isNatKind(activate(N)), activate(N)) [1]
U52(tt, N) → activate(N) [1]
U61(tt, M, N) → U62(isNatKind(activate(M)), activate(M), activate(N)) [1]
U62(tt, M, N) → U63(isNat(activate(N)), activate(M), activate(N)) [1]
U63(tt, M, N) → U64(isNatKind(activate(N)), activate(M), activate(N)) [1]
U64(tt, M, N) → s(plus(activate(N), activate(M))) [1]
isNat(n__0) → tt [1]
isNat(n__plus(V1, V2)) → U11(isNatKind(activate(V1)), activate(V1), activate(V2)) [1]
isNat(n__s(V1)) → U21(isNatKind(activate(V1)), activate(V1)) [1]
isNatKind(n__0) → tt [1]
isNatKind(n__plus(V1, V2)) → U31(isNatKind(activate(V1)), activate(V2)) [1]
isNatKind(n__s(V1)) → U41(isNatKind(activate(V1))) [1]
plus(N, 0') → U51(isNat(N), N) [1]
plus(N, s(M)) → U61(isNat(M), M, N) [1]
0' → n__0 [1]
plus(X1, X2) → n__plus(X1, X2) [1]
s(X) → n__s(X) [1]
activate(n__0) → 0' [1]
activate(n__plus(X1, X2)) → plus(X1, X2) [1]
activate(n__s(X)) → s(X) [1]
activate(X) → X [1]
plus(N, 0') → U51(isNat(N), N) [1]
plus(N, s(M)) → U61(isNat(M), M, N) [1]
0' → n__0 [1]
s(X) → n__s(X) [1]
U11(tt, V1, V2) → U12(isNatKind(activate(V1)), activate(V1), activate(V2)) [1]
U12(tt, V1, V2) → U13(isNatKind(activate(V2)), activate(V1), activate(V2)) [1]
U13(tt, V1, V2) → U14(isNatKind(activate(V2)), activate(V1), activate(V2)) [1]
U14(tt, V1, V2) → U15(isNat(activate(V1)), activate(V2)) [1]
U15(tt, V2) → U16(isNat(activate(V2))) [1]
U16(tt) → tt [1]
U21(tt, V1) → U22(isNatKind(activate(V1)), activate(V1)) [1]
U22(tt, V1) → U23(isNat(activate(V1))) [1]
U23(tt) → tt [1]
U31(tt, V2) → U32(isNatKind(activate(V2))) [1]
U32(tt) → tt [1]
U41(tt) → tt [1]
U51(tt, N) → U52(isNatKind(activate(N)), activate(N)) [1]
U52(tt, N) → activate(N) [1]
U61(tt, M, N) → U62(isNatKind(activate(M)), activate(M), activate(N)) [1]
U62(tt, M, N) → U63(isNat(activate(N)), activate(M), activate(N)) [1]
U63(tt, M, N) → U64(isNatKind(activate(N)), activate(M), activate(N)) [1]
U64(tt, M, N) → s(plus(activate(N), activate(M))) [1]
isNat(n__0) → tt [1]
isNat(n__plus(V1, V2)) → U11(isNatKind(activate(V1)), activate(V1), activate(V2)) [1]
isNat(n__s(V1)) → U21(isNatKind(activate(V1)), activate(V1)) [1]
isNatKind(n__0) → tt [1]
isNatKind(n__plus(V1, V2)) → U31(isNatKind(activate(V1)), activate(V2)) [1]
isNatKind(n__s(V1)) → U41(isNatKind(activate(V1))) [1]
0' → n__0 [1]
plus(X1, X2) → n__plus(X1, X2) [1]
s(X) → n__s(X) [1]
activate(n__0) → 0' [1]
activate(n__plus(X1, X2)) → plus(X1, X2) [1]
activate(n__s(X)) → s(X) [1]
activate(X) → X [1]
U11(tt, V1, V2) → U12(isNatKind(activate(V1)), activate(V1), activate(V2)) [1]
U12(tt, V1, V2) → U13(isNatKind(activate(V2)), activate(V1), activate(V2)) [1]
U13(tt, V1, V2) → U14(isNatKind(activate(V2)), activate(V1), activate(V2)) [1]
U14(tt, V1, V2) → U15(isNat(activate(V1)), activate(V2)) [1]
U15(tt, V2) → U16(isNat(activate(V2))) [1]
U16(tt) → tt [1]
U21(tt, V1) → U22(isNatKind(activate(V1)), activate(V1)) [1]
U22(tt, V1) → U23(isNat(activate(V1))) [1]
U23(tt) → tt [1]
U31(tt, V2) → U32(isNatKind(activate(V2))) [1]
U32(tt) → tt [1]
U41(tt) → tt [1]
U51(tt, N) → U52(isNatKind(activate(N)), activate(N)) [1]
U52(tt, N) → activate(N) [1]
U61(tt, M, N) → U62(isNatKind(activate(M)), activate(M), activate(N)) [1]
U62(tt, M, N) → U63(isNat(activate(N)), activate(M), activate(N)) [1]
U63(tt, M, N) → U64(isNatKind(activate(N)), activate(M), activate(N)) [1]
U64(tt, M, N) → s(plus(activate(N), activate(M))) [1]
isNat(n__0) → tt [1]
isNat(n__plus(V1, V2)) → U11(isNatKind(activate(V1)), activate(V1), activate(V2)) [1]
isNat(n__s(V1)) → U21(isNatKind(activate(V1)), activate(V1)) [1]
isNatKind(n__0) → tt [1]
isNatKind(n__plus(V1, V2)) → U31(isNatKind(activate(V1)), activate(V2)) [1]
isNatKind(n__s(V1)) → U41(isNatKind(activate(V1))) [1]
0' → n__0 [1]
plus(X1, X2) → n__plus(X1, X2) [1]
s(X) → n__s(X) [1]
activate(n__0) → 0' [1]
activate(n__plus(X1, X2)) → plus(X1, X2) [1]
activate(n__s(X)) → s(X) [1]
activate(X) → X [1]
| U11 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → tt tt :: tt U12 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → tt isNatKind :: n__0:n__plus:n__s → tt activate :: n__0:n__plus:n__s → n__0:n__plus:n__s U13 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → tt U14 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → tt U15 :: tt → n__0:n__plus:n__s → tt isNat :: n__0:n__plus:n__s → tt U16 :: tt → tt U21 :: tt → n__0:n__plus:n__s → tt U22 :: tt → n__0:n__plus:n__s → tt U23 :: tt → tt U31 :: tt → n__0:n__plus:n__s → tt U32 :: tt → tt U41 :: tt → tt U51 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s U52 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s U61 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s U62 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s U63 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s U64 :: tt → n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s s :: n__0:n__plus:n__s → n__0:n__plus:n__s plus :: n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s n__0 :: n__0:n__plus:n__s n__plus :: n__0:n__plus:n__s → n__0:n__plus:n__s → n__0:n__plus:n__s n__s :: n__0:n__plus:n__s → n__0:n__plus:n__s 0' :: n__0:n__plus:n__s |
| Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules:
The TRS has the following type information:
Rewrite Strategy: INNERMOST |
tt => 0
n__0 => 0
0' -{ 1 }→ 0 :|:
U11(z, z', z'') -{ 1 }→ U12(isNatKind(activate(V1)), activate(V1), activate(V2)) :|: V1 >= 0, V2 >= 0, z = 0, z'' = V2, z' = V1
U12(z, z', z'') -{ 1 }→ U13(isNatKind(activate(V2)), activate(V1), activate(V2)) :|: V1 >= 0, V2 >= 0, z = 0, z'' = V2, z' = V1
U13(z, z', z'') -{ 1 }→ U14(isNatKind(activate(V2)), activate(V1), activate(V2)) :|: V1 >= 0, V2 >= 0, z = 0, z'' = V2, z' = V1
U14(z, z', z'') -{ 1 }→ U15(isNat(activate(V1)), activate(V2)) :|: V1 >= 0, V2 >= 0, z = 0, z'' = V2, z' = V1
U15(z, z') -{ 1 }→ U16(isNat(activate(V2))) :|: z' = V2, V2 >= 0, z = 0
U16(z) -{ 1 }→ 0 :|: z = 0
U21(z, z') -{ 1 }→ U22(isNatKind(activate(V1)), activate(V1)) :|: V1 >= 0, z = 0, z' = V1
U22(z, z') -{ 1 }→ U23(isNat(activate(V1))) :|: V1 >= 0, z = 0, z' = V1
U23(z) -{ 1 }→ 0 :|: z = 0
U31(z, z') -{ 1 }→ U32(isNatKind(activate(V2))) :|: z' = V2, V2 >= 0, z = 0
U32(z) -{ 1 }→ 0 :|: z = 0
U41(z) -{ 1 }→ 0 :|: z = 0
U51(z, z') -{ 1 }→ U52(isNatKind(activate(N)), activate(N)) :|: z' = N, z = 0, N >= 0
U52(z, z') -{ 1 }→ activate(N) :|: z' = N, z = 0, N >= 0
U61(z, z', z'') -{ 1 }→ U62(isNatKind(activate(M)), activate(M), activate(N)) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0
U62(z, z', z'') -{ 1 }→ U63(isNat(activate(N)), activate(M), activate(N)) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0
U63(z, z', z'') -{ 1 }→ U64(isNatKind(activate(N)), activate(M), activate(N)) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0
U64(z, z', z'') -{ 1 }→ s(plus(activate(N), activate(M))) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0
activate(z) -{ 1 }→ X :|: X >= 0, z = X
activate(z) -{ 1 }→ s(X) :|: z = 1 + X, X >= 0
activate(z) -{ 1 }→ plus(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
activate(z) -{ 1 }→ 0' :|: z = 0
isNat(z) -{ 1 }→ U21(isNatKind(activate(V1)), activate(V1)) :|: z = 1 + V1, V1 >= 0
isNat(z) -{ 1 }→ U11(isNatKind(activate(V1)), activate(V1), activate(V2)) :|: V1 >= 0, V2 >= 0, z = 1 + V1 + V2
isNat(z) -{ 1 }→ 0 :|: z = 0
isNatKind(z) -{ 1 }→ U41(isNatKind(activate(V1))) :|: z = 1 + V1, V1 >= 0
isNatKind(z) -{ 1 }→ U31(isNatKind(activate(V1)), activate(V2)) :|: V1 >= 0, V2 >= 0, z = 1 + V1 + V2
isNatKind(z) -{ 1 }→ 0 :|: z = 0
plus(z, z') -{ 1 }→ 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
s(z) -{ 1 }→ 1 + X :|: X >= 0, z = X
| eq(start(V, V3, V4),0,[fun(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[fun1(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[fun2(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[fun3(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[fun4(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[fun5(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[fun6(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[fun7(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[fun8(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[fun9(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[fun10(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[fun11(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[fun12(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[fun13(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[fun14(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[fun15(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[fun16(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[fun17(V, V3, V4, Out)],[V >= 0,V3 >= 0,V4 >= 0]). eq(start(V, V3, V4),0,[isNat(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[isNatKind(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[fun18(Out)],[]). eq(start(V, V3, V4),0,[plus(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V4),0,[s(V, Out)],[V >= 0]). eq(start(V, V3, V4),0,[activate(V, Out)],[V >= 0]). eq(fun(V, V3, V4, Out),1,[activate(V11, Ret00),isNatKind(Ret00, Ret0),activate(V11, Ret1),activate(V21, Ret2),fun1(Ret0, Ret1, Ret2, Ret)],[Out = Ret,V11 >= 0,V21 >= 0,V = 0,V4 = V21,V3 = V11]). eq(fun1(V, V3, V4, Out),1,[activate(V22, Ret001),isNatKind(Ret001, Ret01),activate(V12, Ret11),activate(V22, Ret21),fun2(Ret01, Ret11, Ret21, Ret3)],[Out = Ret3,V12 >= 0,V22 >= 0,V = 0,V4 = V22,V3 = V12]). eq(fun2(V, V3, V4, Out),1,[activate(V23, Ret002),isNatKind(Ret002, Ret02),activate(V13, Ret12),activate(V23, Ret22),fun3(Ret02, Ret12, Ret22, Ret4)],[Out = Ret4,V13 >= 0,V23 >= 0,V = 0,V4 = V23,V3 = V13]). eq(fun3(V, V3, V4, Out),1,[activate(V14, Ret003),isNat(Ret003, Ret03),activate(V24, Ret13),fun4(Ret03, Ret13, Ret5)],[Out = Ret5,V14 >= 0,V24 >= 0,V = 0,V4 = V24,V3 = V14]). eq(fun4(V, V3, Out),1,[activate(V25, Ret004),isNat(Ret004, Ret04),fun5(Ret04, Ret6)],[Out = Ret6,V3 = V25,V25 >= 0,V = 0]). eq(fun5(V, Out),1,[],[Out = 0,V = 0]). eq(fun6(V, V3, Out),1,[activate(V15, Ret005),isNatKind(Ret005, Ret05),activate(V15, Ret14),fun7(Ret05, Ret14, Ret7)],[Out = Ret7,V15 >= 0,V = 0,V3 = V15]). eq(fun7(V, V3, Out),1,[activate(V16, Ret006),isNat(Ret006, Ret06),fun8(Ret06, Ret8)],[Out = Ret8,V16 >= 0,V = 0,V3 = V16]). eq(fun8(V, Out),1,[],[Out = 0,V = 0]). eq(fun9(V, V3, Out),1,[activate(V26, Ret007),isNatKind(Ret007, Ret07),fun10(Ret07, Ret9)],[Out = Ret9,V3 = V26,V26 >= 0,V = 0]). eq(fun10(V, Out),1,[],[Out = 0,V = 0]). eq(fun11(V, Out),1,[],[Out = 0,V = 0]). eq(fun12(V, V3, Out),1,[activate(N1, Ret008),isNatKind(Ret008, Ret08),activate(N1, Ret15),fun13(Ret08, Ret15, Ret10)],[Out = Ret10,V3 = N1,V = 0,N1 >= 0]). eq(fun13(V, V3, Out),1,[activate(N2, Ret16)],[Out = Ret16,V3 = N2,V = 0,N2 >= 0]). eq(fun14(V, V3, V4, Out),1,[activate(M1, Ret009),isNatKind(Ret009, Ret09),activate(M1, Ret17),activate(N3, Ret23),fun15(Ret09, Ret17, Ret23, Ret18)],[Out = Ret18,V3 = M1,V = 0,V4 = N3,M1 >= 0,N3 >= 0]). eq(fun15(V, V3, V4, Out),1,[activate(N4, Ret0010),isNat(Ret0010, Ret010),activate(M2, Ret19),activate(N4, Ret24),fun16(Ret010, Ret19, Ret24, Ret20)],[Out = Ret20,V3 = M2,V = 0,V4 = N4,M2 >= 0,N4 >= 0]). eq(fun16(V, V3, V4, Out),1,[activate(N5, Ret0011),isNatKind(Ret0011, Ret011),activate(M3, Ret110),activate(N5, Ret25),fun17(Ret011, Ret110, Ret25, Ret26)],[Out = Ret26,V3 = M3,V = 0,V4 = N5,M3 >= 0,N5 >= 0]). eq(fun17(V, V3, V4, Out),1,[activate(N6, Ret0012),activate(M4, Ret012),plus(Ret0012, Ret012, Ret013),s(Ret013, Ret27)],[Out = Ret27,V3 = M4,V = 0,V4 = N6,M4 >= 0,N6 >= 0]). eq(isNat(V, Out),1,[],[Out = 0,V = 0]). eq(isNat(V, Out),1,[activate(V17, Ret0013),isNatKind(Ret0013, Ret014),activate(V17, Ret111),activate(V27, Ret28),fun(Ret014, Ret111, Ret28, Ret29)],[Out = Ret29,V17 >= 0,V27 >= 0,V = 1 + V17 + V27]). eq(isNat(V, Out),1,[activate(V18, Ret0014),isNatKind(Ret0014, Ret015),activate(V18, Ret112),fun6(Ret015, Ret112, Ret30)],[Out = Ret30,V = 1 + V18,V18 >= 0]). eq(isNatKind(V, Out),1,[],[Out = 0,V = 0]). eq(isNatKind(V, Out),1,[activate(V19, Ret0015),isNatKind(Ret0015, Ret016),activate(V28, Ret113),fun9(Ret016, Ret113, Ret31)],[Out = Ret31,V19 >= 0,V28 >= 0,V = 1 + V19 + V28]). eq(isNatKind(V, Out),1,[activate(V110, Ret0016),isNatKind(Ret0016, Ret017),fun11(Ret017, Ret32)],[Out = Ret32,V = 1 + V110,V110 >= 0]). eq(fun18(Out),1,[],[Out = 0]). eq(plus(V, V3, Out),1,[],[Out = 1 + X11 + X21,X11 >= 0,X21 >= 0,V = X11,V3 = X21]). eq(s(V, Out),1,[],[Out = 1 + X3,X3 >= 0,V = X3]). eq(activate(V, Out),1,[fun18(Ret33)],[Out = Ret33,V = 0]). eq(activate(V, Out),1,[plus(X12, X22, Ret34)],[Out = Ret34,X12 >= 0,X22 >= 0,V = 1 + X12 + X22]). eq(activate(V, Out),1,[s(X4, Ret35)],[Out = Ret35,V = 1 + X4,X4 >= 0]). eq(activate(V, Out),1,[],[Out = X5,X5 >= 0,V = X5]). input_output_vars(fun(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(fun1(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(fun2(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(fun3(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(fun4(V,V3,Out),[V,V3],[Out]). input_output_vars(fun5(V,Out),[V],[Out]). input_output_vars(fun6(V,V3,Out),[V,V3],[Out]). input_output_vars(fun7(V,V3,Out),[V,V3],[Out]). input_output_vars(fun8(V,Out),[V],[Out]). input_output_vars(fun9(V,V3,Out),[V,V3],[Out]). input_output_vars(fun10(V,Out),[V],[Out]). input_output_vars(fun11(V,Out),[V],[Out]). input_output_vars(fun12(V,V3,Out),[V,V3],[Out]). input_output_vars(fun13(V,V3,Out),[V,V3],[Out]). input_output_vars(fun14(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(fun15(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(fun16(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(fun17(V,V3,V4,Out),[V,V3,V4],[Out]). input_output_vars(isNat(V,Out),[V],[Out]). input_output_vars(isNatKind(V,Out),[V],[Out]). input_output_vars(fun18(Out),[],[Out]). input_output_vars(plus(V,V3,Out),[V,V3],[Out]). input_output_vars(s(V,Out),[V],[Out]). input_output_vars(activate(V,Out),[V],[Out]). |
CoFloCo proof output:
Preprocessing Cost Relations
=====================================
#### Computed strongly connected components
0. non_recursive : [fun18/1]
1. non_recursive : [plus/3]
2. non_recursive : [s/2]
3. non_recursive : [activate/2]
4. non_recursive : [fun5/2]
5. non_recursive : [fun8/2]
6. non_recursive : [fun11/2]
7. non_recursive : [fun10/2]
8. recursive [non_tail,multiple] : [fun9/3,isNatKind/2]
9. recursive [non_tail,multiple] : [fun/4,fun1/4,fun2/4,fun3/4,fun4/3,fun6/3,fun7/3,isNat/2]
10. non_recursive : [fun13/3]
11. non_recursive : [fun12/3]
12. non_recursive : [fun17/4]
13. non_recursive : [fun16/4]
14. non_recursive : [fun15/4]
15. non_recursive : [fun14/4]
16. non_recursive : [start/3]
#### Obtained direct recursion through partial evaluation
0. SCC is completely evaluated into other SCCs
1. SCC is completely evaluated into other SCCs
2. SCC is completely evaluated into other SCCs
3. SCC is partially evaluated into activate/2
4. SCC is completely evaluated into other SCCs
5. SCC is completely evaluated into other SCCs
6. SCC is completely evaluated into other SCCs
7. SCC is completely evaluated into other SCCs
8. SCC is partially evaluated into isNatKind/2
9. SCC is partially evaluated into isNat/2
10. SCC is completely evaluated into other SCCs
11. SCC is partially evaluated into fun12/3
12. SCC is partially evaluated into fun17/4
13. SCC is partially evaluated into fun16/4
14. SCC is partially evaluated into fun15/4
15. SCC is partially evaluated into fun14/4
16. SCC is partially evaluated into start/3
Control-Flow Refinement of Cost Relations
=====================================
### Specialization of cost equations activate/2
* CE 19 is refined into CE [33]
* CE 20 is refined into CE [34]
* CE 21 is refined into CE [35]
### Cost equations --> "Loop" of activate/2
* CEs [33,34,35] --> Loop 14
### Ranking functions of CR activate(V,Out)
#### Partial ranking functions of CR activate(V,Out)
### Specialization of cost equations isNatKind/2
* CE 24 is refined into CE [36]
* CE 23 is refined into CE [37]
* CE 22 is refined into CE [38]
### Cost equations --> "Loop" of isNatKind/2
* CEs [38] --> Loop 15
* CEs [37] --> Loop 16
* CEs [36] --> Loop 17
### Ranking functions of CR isNatKind(V,Out)
* RF of phase [15,17]: [V]
#### Partial ranking functions of CR isNatKind(V,Out)
* Partial RF of phase [15,17]:
- RF of loop [15:1,15:2,17:1]:
V
### Specialization of cost equations isNat/2
* CE 27 is refined into CE [39]
* CE 26 is refined into CE [40,41,42,43]
* CE 25 is refined into CE [44,45]
### Cost equations --> "Loop" of isNat/2
* CEs [45] --> Loop 18
* CEs [44] --> Loop 19
* CEs [43] --> Loop 20
* CEs [42] --> Loop 21
* CEs [41] --> Loop 22
* CEs [40] --> Loop 23
* CEs [39] --> Loop 24
### Ranking functions of CR isNat(V,Out)
* RF of phase [18,20,21,22]: [V-1]
#### Partial ranking functions of CR isNat(V,Out)
* Partial RF of phase [18,20,21,22]:
- RF of loop [18:1,21:1,21:2,22:1,22:2]:
V-1
- RF of loop [20:1,20:2]:
V/2-1
### Specialization of cost equations fun12/3
* CE 28 is refined into CE [46,47]
### Cost equations --> "Loop" of fun12/3
* CEs [47] --> Loop 25
* CEs [46] --> Loop 26
### Ranking functions of CR fun12(V,V3,Out)
#### Partial ranking functions of CR fun12(V,V3,Out)
### Specialization of cost equations fun17/4
* CE 32 is refined into CE [48]
### Cost equations --> "Loop" of fun17/4
* CEs [48] --> Loop 27
### Ranking functions of CR fun17(V,V3,V4,Out)
#### Partial ranking functions of CR fun17(V,V3,V4,Out)
### Specialization of cost equations fun16/4
* CE 31 is refined into CE [49,50]
### Cost equations --> "Loop" of fun16/4
* CEs [50] --> Loop 28
* CEs [49] --> Loop 29
### Ranking functions of CR fun16(V,V3,V4,Out)
#### Partial ranking functions of CR fun16(V,V3,V4,Out)
### Specialization of cost equations fun15/4
* CE 30 is refined into CE [51,52,53]
### Cost equations --> "Loop" of fun15/4
* CEs [53] --> Loop 30
* CEs [52] --> Loop 31
* CEs [51] --> Loop 32
### Ranking functions of CR fun15(V,V3,V4,Out)
#### Partial ranking functions of CR fun15(V,V3,V4,Out)
### Specialization of cost equations fun14/4
* CE 29 is refined into CE [54,55,56,57,58,59]
### Cost equations --> "Loop" of fun14/4
* CEs [59] --> Loop 33
* CEs [58] --> Loop 34
* CEs [57] --> Loop 35
* CEs [56] --> Loop 36
* CEs [55] --> Loop 37
* CEs [54] --> Loop 38
### Ranking functions of CR fun14(V,V3,V4,Out)
#### Partial ranking functions of CR fun14(V,V3,V4,Out)
### Specialization of cost equations start/3
* CE 2 is refined into CE [60,61,62]
* CE 3 is refined into CE [63,64,65]
* CE 4 is refined into CE [66,67,68,69,70,71,72,73,74]
* CE 5 is refined into CE [75,76,77,78,79,80,81,82,83]
* CE 6 is refined into CE [84,85,86,87,88,89,90,91,92]
* CE 7 is refined into CE [93,94,95,96,97,98,99,100,101]
* CE 8 is refined into CE [102,103]
* CE 9 is refined into CE [104]
* CE 10 is refined into CE [105,106]
* CE 11 is refined into CE [107]
* CE 12 is refined into CE [108,109,110,111,112,113]
* CE 13 is refined into CE [114,115,116]
* CE 14 is refined into CE [117,118]
* CE 15 is refined into CE [119]
* CE 16 is refined into CE [120,121,122]
* CE 17 is refined into CE [123,124]
* CE 18 is refined into CE [125]
### Cost equations --> "Loop" of start/3
* CEs [60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125] --> Loop 39
### Ranking functions of CR start(V,V3,V4)
#### Partial ranking functions of CR start(V,V3,V4)
Computing Bounds
=====================================
#### Cost of chains of activate(V,Out):
* Chain [14]: 2
with precondition: [V=Out,V>=0]
#### Cost of chains of isNatKind(V,Out):
* Chain [16]: 1
with precondition: [V=0,Out=0]
* Chain [multiple([15,17],[[16]])]: 13*it(15)+1*it([16])+0
Such that:it([16]) =< V+1
aux(1) =< V
it(15) =< aux(1)
with precondition: [Out=0,V>=1]
#### Cost of chains of isNat(V,Out):
* Chain [24]: 1
with precondition: [V=0,Out=0]
* Chain [multiple(23,[[24]])]: 43
with precondition: [V=1,Out=0]
* Chain [19,24]: 17
with precondition: [V=1,Out=0]
* Chain [multiple([18,20,21,22],[[24],[multiple(23,[[24]])],[19,24]])]: 14*it(18)+37*it(20)+78*it(21)+61*it([19,24])+2*s(49)+26*s(50)+30*s(53)+26*s(55)+4*s(59)+52*s(60)+0
Such that:aux(31) =< 1
aux(32) =< V
aux(33) =< V/2
aux(34) =< 2/3*V
it(18) =< aux(32)
it(20) =< aux(32)
it(21) =< aux(32)
it(20) =< aux(33)
it(21) =< aux(34)
aux(14) =< aux(32)+1
aux(16) =< aux(32)
aux(17) =< aux(32)-1
it([19,24]) =< it(21)+it(21)+it(20)+aux(31)
s(62) =< it(21)*aux(14)
s(61) =< it(21)*aux(16)
s(57) =< it(20)*aux(16)
s(56) =< it(20)*aux(17)
s(52) =< it(18)*aux(14)
s(51) =< it(18)*aux(32)
s(59) =< s(62)
s(60) =< s(61)
s(53) =< s(57)
s(55) =< s(56)
s(49) =< s(52)
s(50) =< s(51)
with precondition: [Out=0,V>=2]
#### Cost of chains of fun12(V,V3,Out):
* Chain [26]: 9
with precondition: [V=0,V3=0,Out=0]
* Chain [25]: 1*s(67)+13*s(69)+8
Such that:s(68) =< V3
s(67) =< V3+1
s(69) =< s(68)
with precondition: [V=0,V3=Out,V3>=1]
#### Cost of chains of fun17(V,V3,V4,Out):
* Chain [27]: 7
with precondition: [V=0,V3+V4+2=Out,V3>=0,V4>=0]
#### Cost of chains of fun16(V,V3,V4,Out):
* Chain [29]: 15
with precondition: [V=0,V4=0,V3+2=Out,V3>=0]
* Chain [28]: 1*s(70)+13*s(72)+14
Such that:s(71) =< V4
s(70) =< V4+1
s(72) =< s(71)
with precondition: [V=0,V3+V4+2=Out,V3>=0,V4>=1]
#### Cost of chains of fun15(V,V3,V4,Out):
* Chain [32]: 23
with precondition: [V=0,V4=0,V3+2=Out,V3>=0]
* Chain [31]: 1*s(74)+13*s(75)+64
Such that:s(73) =< 1
s(74) =< 2
s(75) =< s(73)
with precondition: [V=0,V4=1,V3+3=Out,V3>=0]
* Chain [30]: 27*s(80)+37*s(81)+78*s(82)+61*s(86)+4*s(93)+52*s(94)+30*s(95)+26*s(96)+2*s(97)+26*s(98)+1*s(100)+21
Such that:s(76) =< 1
s(100) =< V4+1
s(78) =< V4/2
s(79) =< 2/3*V4
aux(35) =< V4
s(80) =< aux(35)
s(81) =< aux(35)
s(82) =< aux(35)
s(81) =< s(78)
s(82) =< s(79)
s(83) =< aux(35)+1
s(84) =< aux(35)
s(85) =< aux(35)-1
s(86) =< s(82)+s(82)+s(81)+s(76)
s(87) =< s(82)*s(83)
s(88) =< s(82)*s(84)
s(89) =< s(81)*s(84)
s(90) =< s(81)*s(85)
s(91) =< s(80)*s(83)
s(92) =< s(80)*aux(35)
s(93) =< s(87)
s(94) =< s(88)
s(95) =< s(89)
s(96) =< s(90)
s(97) =< s(91)
s(98) =< s(92)
with precondition: [V=0,V3+V4+2=Out,V3>=0,V4>=2]
#### Cost of chains of fun14(V,V3,V4,Out):
* Chain [38]: 31
with precondition: [V=0,V3=0,V4=0,Out=2]
* Chain [37]: 1*s(103)+13*s(104)+72
Such that:s(102) =< 1
s(103) =< 2
s(104) =< s(102)
with precondition: [V=0,V3=0,V4=1,Out=3]
* Chain [36]: 1*s(106)+27*s(110)+37*s(111)+78*s(112)+61*s(116)+4*s(123)+52*s(124)+30*s(125)+26*s(126)+2*s(127)+26*s(128)+29
Such that:s(105) =< 1
s(109) =< V4
s(106) =< V4+1
s(107) =< V4/2
s(108) =< 2/3*V4
s(110) =< s(109)
s(111) =< s(109)
s(112) =< s(109)
s(111) =< s(107)
s(112) =< s(108)
s(113) =< s(109)+1
s(114) =< s(109)
s(115) =< s(109)-1
s(116) =< s(112)+s(112)+s(111)+s(105)
s(117) =< s(112)*s(113)
s(118) =< s(112)*s(114)
s(119) =< s(111)*s(114)
s(120) =< s(111)*s(115)
s(121) =< s(110)*s(113)
s(122) =< s(110)*s(109)
s(123) =< s(117)
s(124) =< s(118)
s(125) =< s(119)
s(126) =< s(120)
s(127) =< s(121)
s(128) =< s(122)
with precondition: [V=0,V3=0,V4+2=Out,V4>=2]
* Chain [35]: 1*s(129)+13*s(131)+30
Such that:s(130) =< V3
s(129) =< V3+1
s(131) =< s(130)
with precondition: [V=0,V4=0,V3+2=Out,V3>=1]
* Chain [34]: 1*s(132)+13*s(134)+1*s(136)+13*s(137)+71
Such that:s(135) =< 1
s(136) =< 2
s(133) =< V3
s(132) =< V3+1
s(137) =< s(135)
s(134) =< s(133)
with precondition: [V=0,V4=1,V3+3=Out,V3>=1]
* Chain [33]: 1*s(138)+13*s(140)+1*s(142)+27*s(146)+37*s(147)+78*s(148)+61*s(152)+4*s(159)+52*s(160)+30*s(161)+26*s(162)+2*s(163)+26*s(164)+28
Such that:s(141) =< 1
s(139) =< V3
s(138) =< V3+1
s(145) =< V4
s(142) =< V4+1
s(143) =< V4/2
s(144) =< 2/3*V4
s(146) =< s(145)
s(147) =< s(145)
s(148) =< s(145)
s(147) =< s(143)
s(148) =< s(144)
s(149) =< s(145)+1
s(150) =< s(145)
s(151) =< s(145)-1
s(152) =< s(148)+s(148)+s(147)+s(141)
s(153) =< s(148)*s(149)
s(154) =< s(148)*s(150)
s(155) =< s(147)*s(150)
s(156) =< s(147)*s(151)
s(157) =< s(146)*s(149)
s(158) =< s(146)*s(145)
s(159) =< s(153)
s(160) =< s(154)
s(161) =< s(155)
s(162) =< s(156)
s(163) =< s(157)
s(164) =< s(158)
s(140) =< s(139)
with precondition: [V=0,V3+V4+2=Out,V3>=1,V4>=2]
#### Cost of chains of start(V,V3,V4):
* Chain [39]: 22*s(165)+286*s(167)+9*s(168)+313*s(170)+518*s(176)+1092*s(177)+854*s(181)+56*s(188)+728*s(189)+420*s(190)+364*s(191)+28*s(192)+364*s(193)+19*s(223)+457*s(225)+555*s(234)+1170*s(235)+915*s(239)+60*s(246)+780*s(247)+450*s(248)+390*s(249)+30*s(250)+390*s(251)+27*s(980)+37*s(981)+78*s(982)+61*s(986)+4*s(993)+52*s(994)+30*s(995)+26*s(996)+2*s(997)+26*s(998)+1*s(999)+116
Such that:s(999) =< V+1
s(978) =< V/2
s(979) =< 2/3*V
aux(73) =< 1
aux(74) =< 2
aux(75) =< V
aux(76) =< V3
aux(77) =< V3+1
aux(78) =< V3/2
aux(79) =< 2/3*V3
aux(80) =< V4
aux(81) =< V4+1
aux(82) =< V4/2
aux(83) =< 2/3*V4
s(165) =< aux(74)
s(168) =< aux(77)
s(223) =< aux(81)
s(167) =< aux(73)
s(170) =< aux(76)
s(176) =< aux(76)
s(177) =< aux(76)
s(176) =< aux(78)
s(177) =< aux(79)
s(178) =< aux(76)+1
s(179) =< aux(76)
s(180) =< aux(76)-1
s(181) =< s(177)+s(177)+s(176)+aux(73)
s(182) =< s(177)*s(178)
s(183) =< s(177)*s(179)
s(184) =< s(176)*s(179)
s(185) =< s(176)*s(180)
s(186) =< s(170)*s(178)
s(187) =< s(170)*aux(76)
s(188) =< s(182)
s(189) =< s(183)
s(190) =< s(184)
s(191) =< s(185)
s(192) =< s(186)
s(193) =< s(187)
s(225) =< aux(80)
s(234) =< aux(80)
s(235) =< aux(80)
s(234) =< aux(82)
s(235) =< aux(83)
s(236) =< aux(80)+1
s(237) =< aux(80)
s(238) =< aux(80)-1
s(239) =< s(235)+s(235)+s(234)+aux(73)
s(240) =< s(235)*s(236)
s(241) =< s(235)*s(237)
s(242) =< s(234)*s(237)
s(243) =< s(234)*s(238)
s(244) =< s(225)*s(236)
s(245) =< s(225)*aux(80)
s(246) =< s(240)
s(247) =< s(241)
s(248) =< s(242)
s(249) =< s(243)
s(250) =< s(244)
s(251) =< s(245)
s(980) =< aux(75)
s(981) =< aux(75)
s(982) =< aux(75)
s(981) =< s(978)
s(982) =< s(979)
s(983) =< aux(75)+1
s(984) =< aux(75)
s(985) =< aux(75)-1
s(986) =< s(982)+s(982)+s(981)+aux(73)
s(987) =< s(982)*s(983)
s(988) =< s(982)*s(984)
s(989) =< s(981)*s(984)
s(990) =< s(981)*s(985)
s(991) =< s(980)*s(983)
s(992) =< s(980)*aux(75)
s(993) =< s(987)
s(994) =< s(988)
s(995) =< s(989)
s(996) =< s(990)
s(997) =< s(991)
s(998) =< s(992)
with precondition: []
Closed-form bounds of start(V,V3,V4):
-------------------------------------
* Chain [39] with precondition: []
- Upper bound: nat(V)*331+2276+nat(V)*114*nat(V)+nat(V3)*4569+nat(V3)*1596*nat(V3)+nat(V4)*5017+nat(V4)*1710*nat(V4)+nat(nat(V)+ -1)*26*nat(V)+nat(nat(V3)+ -1)*364*nat(V3)+nat(nat(V4)+ -1)*390*nat(V4)+nat(V+1)+nat(V3+1)*9+nat(V4+1)*19
- Complexity: n^2
### Maximum cost of start(V,V3,V4): nat(V)*331+2276+nat(V)*114*nat(V)+nat(V3)*4569+nat(V3)*1596*nat(V3)+nat(V4)*5017+nat(V4)*1710*nat(V4)+nat(nat(V)+ -1)*26*nat(V)+nat(nat(V3)+ -1)*364*nat(V3)+nat(nat(V4)+ -1)*390*nat(V4)+nat(V+1)+nat(V3+1)*9+nat(V4+1)*19
Asymptotic class: n^2
* Total analysis performed in 3117 ms.